1. Technical Field
The present invention is directed to an apparatus and method for determining buffered Steiner trees for complex circuits.
2. Description of Related Art
It is now widely accepted that interconnect performance is becoming increasingly dominant over transistor and logic performance in the deep submicron regime. Buffer insertion is now a fundamental technology used in modern VLSI design methodologies. As gate delays decrease with increasing chip dimensions, however, the number of buffers required quickly rises. It is expected that close to 800,000 buffers will be required for 50 nanometer technologies. It is critical to automate the entire interconnect optimization process to efficiently achieve timing closure.
The problem of inserting buffers to reduce the delay on signal nets has been recognized and studied. A closed form solutions for two-pin nets have been proposed by van Ginneken. Van Ginneken""s dynamic programming algorithm, described in xe2x80x9cBuffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,xe2x80x9d Int""l Symposium on Circuits and Systems, 1990, pp. 865-868, which is hereby incorporated by reference, has become a classic in the field. Given a fixed Steiner tree topology, the van Ginneken algorithm finds the optimal buffer placement on the topology under an Elmore delay model for a single buffer type and simple gate delay model. Several extensions to this work have been proposed. Together, these enhancements make the van Ginneken style of buffer insertion quite potent as it can handle many constraints, buffer types, and delay models, while retaining optimality under many of these conditions. Most recently, research on buffer insertion has focused on accommodating various types of blockage constraints.
The primary shortcoming with the van Ginneken style of buffer insertion is that it is limited by the given Steiner topology. Thus, buffer insertion has been combined with Steiner tree constructions using a two-step approach of first constructing a Steiner tree, then running van Ginneken style buffer insertion. An optimal solution can be realized using the two-step approach if one uses the xe2x80x9crightxe2x80x9d Steiner tree (i.e., the tree resulting from ripping buffers out of the optimal solution) since the buffer insertion step is optimal. Of course, finding the right tree is difficult since the buffer insertion objective cannot be directly optimized.
The problem of obtaining the xe2x80x9crightxe2x80x9d Steiner tree becomes even more difficult as the complexity of the circuit design increases. Thus, it would be beneficial to have an apparatus and method of identifying an optimal Steiner tree for complex circuit designs.
The present invention provides an apparatus and method for determining buffered Steiner trees for complex circuits. The apparatus and method first clusters sinks with similar characteristics such as criticality, polarity and distance. The purpose of this step is to potentially isolate positive sinks from negative ones and non-critical sinks from critical ones. The present invention then constructs low-level Steiner trees over each of these clusters. Finally, a top-level timing driven Steiner tree is computed where each cluster is treated as a sink. The top-level tree is then merged with the low-level trees to yield a solution for the entire net.